1073B - Vasya and Books - CodeForces Solution


implementation math *1000

Please click on ads to support us..

Python Code:


from math import gcd
from bisect import bisect_left, bisect_right
from itertools import combinations
from itertools import permutations
from bisect import bisect_left
from math import ceil
from heapq import heapify, heappush, heappop, nsmallest
import bisect
from math import pi
from collections import deque
from math import factorial
from math import log, ceil
from collections import defaultdict
from math import *
from sys import stdin, stdout
import itertools
import os
import sys
import threading
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import *
from fractions import Fraction
mod = int(pow(10, 9)+7)


def ii(): return int(input())


def si(): return str(input())


def mi(): return map(int, input().split())


def li1(): return list(mi())


def fii(): return int(stdin.readline())


def fsi(): return str(stdin.readline())


def fmi(): return map(int, stdin.readline().split())


def fli(): return list(fmi())


abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12,
    'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24,
    'z': 25}


def getKey(item): return item[0]


def sort2(l): return sorted(l, key=getKey)


def d2(n, m, num): return [[num for x in range(m)] for y in range(n)]


def isPowerOfTwo(x): return (x and (not (x & (x - 1))))


def decimalToBinary(n): return bin(n).replace("0b", "")


def ntl(n): return [int(i) for i in str(n)]


def powerMod(x, y, p):
    res = 1
    x %= p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res


graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000


def bfs(d, v):
    q = []
    q.append(v)
    visited[v] = 1
    while len(q) != 0:
        x = q[0]
        q.pop(0)
        for i in d[x]:
            if visited[i] != 1:
                visited[i] = 1
                q.append(i)
        print(x)


def make_graph(e):
    d = {}
    for i in range(e):
        x, y = mi()
        if x not in d:
            d[x] = [y]
        else:
            d[x].append(y)
        if y not in d:
            d[y] = [x]
        else:
            d[y].append(x)
    return d


def gr2(n):
    d = defaultdict(list)
    for i in range(n):
        x, y = mi()
        d[x].append(y)
    return d


def connected_components(graph):
    seen = set()

    def dfs(v):
        vs = set([v])
        component = []
        while vs:
            v = vs.pop()
            seen.add(v)
            vs |= set(graph[v]) - seen
            component.append(v)
        return component

    ans = []
    for v in graph:
        if v not in seen:
            d = dfs(v)
            ans.append(d)
    return ans


def primeFactors(n):
    s = set()
    while n % 2 == 0:
        s.add(2)
        n = n // 2
    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0 and i % 2 == 1:
            s.add(i)
            n = n // i
    if n > 2 and n % 2 == 1:
        s.add(n)
    return s


def find_all(a_str, sub):
    start = 0
    while True:
        start = a_str.find(sub, start)
        if start == -1:
            return
        yield start
        start += len(sub)


def SieveOfEratosthenes(n, isPrime):
    isPrime[0] = isPrime[1] = False
    for i in range(2, n):
        isPrime[i] = True
    p = 2
    while (p * p <= n):
        if (isPrime[p] == True):
            i = p * p
            while (i <= n):
                isPrime[i] = False
                i += p
        p += 1
    return isPrime


def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l, r, c in edges:
        g[l].append((c, r))

    q, seen, mins = [(0, f, ())], set(), {f: 0}
    while q:
        (cost, v1, path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t:
                return (cost, path)

            for c, v2 in g.get(v1, ()):
                if v2 in seen:
                    continue
                prev = mins.get(v2, None)
                next = cost + c
                if prev is None or next < prev:
                    mins[v2] = next
                    heappush(q, (next, v2, path))
    return float("inf")


def binsearch(a, l, r, x):
    while l <= r:
        mid = l + (r-1)//2
        if a[mid]:
            return mid
        elif a[mid] > x:
            l = mid-1
        else:
            r = mid+1
    return -1




def readTree(n):
    adj = [set() for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    return adj


def treeOrderByDepth(n, adj, root=0):
    parent = [-2] + [-1]*(n-1)
    ordered = []
    q = deque()
    q.append(root)
    depth = [0] * n
    while q:
        c = q.popleft()
        ordered.append(c)
        for a in adj[c]:
            if parent[a] == -1:
                parent[a] = c
                depth[a] = depth[c] + 1
                q.append(a)
    return (ordered, parent, depth)


def isSubSequence(str1, str2):
    m = len(str1)
    n = len(str2)
    j = 0
    i = 0
    while j < m and i < n:
        if str1[j] == str2[i]:
            j = j+1
        i = i + 1
    return j == m


def nextPowerOf2(n):
    count = 0
    if (n and not(n & (n - 1))):
        return n
    while(n != 0):
        n >>= 1
        count += 1
    return 1 << count


def lastPowerOf2(n):
    count = -1
    if (n and not(n & (n - 1))):
        return n
    while(n != 0):
        n >>= 1
        count += 1
    return 1 << count


def cou(n):
    c = 0
    while n > 1:
        c += 1
        n //= 2
    return c


def sortsec(l):
    return sorted(l, key=lambda x: x[1])


def BinarySearch(a, x):
    i = bisect_left(a, x)
    if i:
        return (i-1)
    else:
        return - 1


def subarray(A):
    r = set()

    p = {0}

    for x in A:
        p = {x | y for y in p} | {x}
        r |= p

    return len(r)


def setBitNumber(n):
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n = n + 1
    return (n >> 1)


def countSetBits(n):
    count = 0
    while (n):
        count += n & 1
        n >>= 1
    return count


def allsub(l):
    n = len(l)
    a = []
    for i in range(n - 1):
        a.append([l[:i], l[i:]])
        a.append([l[i:], l[:i]])
    return a


def closestMultiple(n, x):
    if x > n:
        return x
    z = (int)(x / 2)
    n = n + z
    n = n - (n % x)
    return n


def block(x):
    v = []
    res = []
    while (x > 0):
        v.append(int(x % 2))
        x = int(x / 2)
    for i in range(0, len(v)):
        if (v[i] == 1):
            res.append(i)
    return res

def gen(n):

    l=[]
    for bi in range(2**n + 1):
        x=decimalToBinary(bi)
        x='0'*(n-len(x))+x
        l.append(x)
    return l

n=ii()
l=li1()
m=li1()

ans=[]
j=0
d=defaultdict(int)
for i in range(n):
    c=0
    if d[m[i]]==1:
        ans.append(0)
        continue

    while j<n:
        c+=1
        d[l[j]]=1
        if m[i]==l[j]:
            j+=1
            break
        j+=1
    ans.append(c)
print(*ans)

C++ Code:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// less,greater,less_equal.....
#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f(i, a, n) for (int i = (a); i <= (n); i++)
#define ff first
#define ss second
#define UWU ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> orderd_set; // find_by_order, order_of_key
const ll N = 2e5 + 7, mod = 998244353, inf = 1e12;
ll add(ll a, ll b)
{
    return ((a % mod) + (b % mod)) % mod;
}
ll mult(ll a, ll b)
{
    return ((a % mod) * (b % mod)) % mod;
}
ll expo(ll x, ll y)
{
    ll z = 1;
    while (y)
    {
        if (y % 2 == 1)
            z = mult(z, x);
        x = mult(x, x);
        y /= 2;
    }
    return z;
}

void solve()
{
    int n, x;
    cin >> n;
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        q.push(x);
    }
    vector<bool> vis(n + 3, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        if (vis[x])
        {
            cout << "0 ";
        }
        else
        {
            int cnt = 0;
            while (!q.empty())
            {
                int f = q.front();
                q.pop();
                cnt++;
                vis[f] = 1;
                if (f == x)
                    break;
            }
            cout << cnt << " ";
        }
    }
    cout << "\n";
}
int main()
{
    UWU;
    int tc = 1;
    // cin >> tc;
    cout << fixed << setprecision(6);
    while (tc--)
    {

        solve();
    }
}
/*

*/


Comments

Submit
0 Comments
More Questions

MATCHES Playing with Matches
HRDSEQ Hard Sequence
DRCHEF Doctor Chef
559. Maximum Depth of N-ary Tree
821. Shortest Distance to a Character
1441. Build an Array With Stack Operations
1356. Sort Integers by The Number of 1 Bits
922. Sort Array By Parity II
344. Reverse String
1047. Remove All Adjacent Duplicates In String
977. Squares of a Sorted Array
852. Peak Index in a Mountain Array
461. Hamming Distance
1748. Sum of Unique Elements
897. Increasing Order Search Tree
905. Sort Array By Parity
1351. Count Negative Numbers in a Sorted Matrix
617. Merge Two Binary Trees
1450. Number of Students Doing Homework at a Given Time
700. Search in a Binary Search Tree
590. N-ary Tree Postorder Traversal
589. N-ary Tree Preorder Traversal
1299. Replace Elements with Greatest Element on Right Side
1768. Merge Strings Alternately
561. Array Partition I
1374. Generate a String With Characters That Have Odd Counts
1822. Sign of the Product of an Array
1464. Maximum Product of Two Elements in an Array
1323. Maximum 69 Number
832. Flipping an Image